package com.xufx.algorithm.temTest;

import java.util.HashMap;
import java.util.Map;

class Test {
    static Map<Character, Integer> need = new HashMap();
    static Map<Character, Integer> window = new HashMap();
    public static String minWindow(String s, String t) {
        String res = "";
        Integer temResSize = Integer.MAX_VALUE;
        // 滑动窗口的方式
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int left = 0;
        int right = 0;
        int m = ss.length;
        int n = tt.length;

        for(int i = 0; i < n; i++){
            Integer count = need.get(tt[i]);
            if(count == null){
                need.put(tt[i], 1);
            }else{
                need.put(tt[i], count + 1);
            }
        }

        while(right < m){
            if(right == ss.length){
                continue;
            }
            Integer count = window.get(ss[right]);
            if(count == null){
                window.put(ss[right], 1);
            }else{
                window.put(ss[right], count + 1);
            }
            right++;
            while(check()){
                if(right - left< temResSize){
                    temResSize = right - left;
                    res = s.substring(left, right);
                }
                count = window.get(ss[left]);
                if(count > 1){
                    window.put(ss[left], count - 1);
                }else{
                    window.remove(ss[left]);
                }
                left++;
            }
        }
        System.out.println(res);
        return res;
    }

    public static boolean check(){
        for(Map.Entry<Character, Integer> entry: need.entrySet()){
            Integer needval = entry.getValue();
            Integer windowval = window.get(entry.getKey());
            if(windowval == null || needval > windowval){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        minWindow(s, t);

    }
}